#include "find_min_dist.h"

//! Main function
double findBestPlace( int metodo, const T_ADJ& grafo, int threads )
{
    // Vertex to vertex distance
    T_GRAPH vv_distance(grafo.size(), std::vector<int>(grafo.size(),0));

    switch (metodo)
    {
        // Sequential veresion
        case 0:
            VertToVertDistanceSeq(vv_distance, grafo);
            return MinMaxDistance(vv_distance);

        // Parallel veresion 1
        case 1:
            VertToVertDistanceParal1(vv_distance, grafo, threads);
            return MinMaxDistanceParal(vv_distance);

        // Parallel veresion 2
        case 2:
            VertToVertDistanceParal2(vv_distance, grafo, threads);
            return MinMaxDistanceParal(vv_distance);

        // Parallel veresion 3
        case 3:
            VertToVertDistanceParal3(vv_distance, grafo, threads);
            return MinMaxDistanceParal(vv_distance);

        default:
            exit(9);
    }
}

//! Dijkstra algorithm
void dijkstra_to(int node, T_GRAPH& vv_dist, const T_ADJ& grafo)
{

    std::vector<int> min_distance(grafo.size(), -1);
    min_distance[node] = 0;

    std::set< Line > to_visit;
    to_visit.insert(Line(node, min_distance[node]));

    while (!to_visit.empty())
    {
        Line cur = *to_visit.begin();
        to_visit.erase(to_visit.begin());

        // Visit adj nodes
        const std::vector<Line> &adj = grafo[cur.node];
        for (std::vector<Line>::const_iterator it = adj.begin(); it != adj.end(); ++it)
        {
            const int v = it->node;
            const int minv = min_distance[it->node];
            int dist_acum = cur.c + it->c;

            // -1 = no value assigned = infinite
            if (minv == -1 || dist_acum < minv)
            {
                to_visit.erase(Line(v, minv));

                vv_dist[node][v] = dist_acum;
                min_distance[v] = dist_acum;
                to_visit.insert(Line(v, dist_acum));
            }
        }
    }
}

//!-------------------------------------
//! Sequencial
//!-------------------------------------

//! Find max distance for each vertex
int MinMaxDistance(const T_GRAPH& vv_dist )
{
    std::vector<int> maxdist(vv_dist.size(), -1);
    int min = -1;


    for (size_t i = 0; i < vv_dist.size(); ++i)
    {
        for (size_t j = 0; j < vv_dist.size(); ++j){

            if (maxdist[i] == -1 || maxdist[i] < vv_dist[i][j])
                maxdist[i] = vv_dist[i][j];
        }

        if (min == -1 || min > maxdist[i])
            min = maxdist[i];
    }

    return min;
}

//! Find min distance among all vertex
void VertToVertDistanceSeq( T_GRAPH& vv_dist, const T_ADJ& grafo )
{
    int n = grafo.size();

    for (int i = 0; i < n; ++i)
    {
        dijkstra_to(i, vv_dist, grafo);
    }
}

//!-------------------------------------
//! Parallel
//!-------------------------------------

//! Find max distance for each vertex
int MinMaxDistanceParal(const T_GRAPH& vv_dist )
{
    std::vector<int> maxdist(vv_dist.size(), -1);
    int min = -1;

    #pragma omp parallel for shared(vv_dist, maxdist)
    for (size_t i = 0; i < vv_dist.size(); ++i)
    {
        for (size_t j = 0; j < vv_dist.size(); ++j){

            if (maxdist[i] == -1 || maxdist[i] < vv_dist[i][j])
                maxdist[i] = vv_dist[i][j];
        }
    }

    for (size_t i = 0; i < vv_dist.size(); ++i)
        if (min == -1 || min > maxdist[i])
            min = maxdist[i];

    return min;
}

//! - - - Veresion 1 - - -

//! Find min distance among all vertex
void VertToVertDistanceParal1( T_GRAPH& vv_dist, const T_ADJ& grafo, int threads )
{
    int n = grafo.size();

    omp_set_num_threads(threads);

    #pragma omp parallel for shared(grafo, vv_dist)
    for (int i = 0; i < n; ++i)
    {
        dijkstra_to(i, vv_dist, grafo);
    }
}

//! - - - Veresion 2 - - -

//! Find min distance among all vertex
void VertToVertDistanceParal2( T_GRAPH& vv_dist, const T_ADJ& grafo, int threads )
{
    int n = grafo.size();

    omp_set_num_threads(threads);

    for (int i = 0; i < n; ++i)
    {
        std::vector<int> min_distance(grafo.size(), -1);
        min_distance[i] = 0;

        std::set< Line > to_visit;
        to_visit.insert(Line(i, min_distance[i]));

        while (!to_visit.empty())
        {
            Line cur = *to_visit.begin();
            to_visit.erase(to_visit.begin());

            // Visit adj nodes
            const std::vector<Line> &adj = grafo[cur.node];
            #pragma omp parallel for shared(vv_dist, min_distance)
            for (size_t j = 0; j < adj.size(); ++j)
            {
                int minv;
                const int v = adj[j].node;

                #pragma omp critical (mindst_critical)
                {
                    minv = min_distance[adj[j].node];
                }

                int dist_acum = cur.c + adj[j].c;

                // -1 = no value assigned = infinite
                if (minv == -1 || dist_acum < minv)
                {
                    #pragma omp critical (mindst_critical)
                    {
                        to_visit.erase(Line(v, minv));
                        vv_dist[i][v] = dist_acum;
                        min_distance[v] = dist_acum;
                        to_visit.insert(Line(v, dist_acum));
                    }
                }
            }
        }
    }
}

//! - - - Veresion 3 - - -

//! Find min distance among all vertex
void VertToVertDistanceParal3( T_GRAPH& vv_dist, const T_ADJ& grafo, int threads )
{
    int n = grafo.size();

    omp_set_num_threads(threads);

    #pragma omp parallel for shared(vv_dist, grafo)
    for (int i = 0; i < n; ++i)
    {
        std::vector<int> min_distance(grafo.size(), -1);
        min_distance[i] = 0;

        std::set< Line > to_visit;
        to_visit.insert(Line(i, min_distance[i]));

        while (!to_visit.empty())
        {
            Line cur = *to_visit.begin();
            to_visit.erase(to_visit.begin());

            // Visit adj nodes
            const std::vector<Line> &adj = grafo[cur.node];
            #pragma omp parallel for shared(vv_dist, min_distance)
            for (size_t j = 0; j < adj.size(); ++j)
            {
                int minv;
                const int v = adj[j].node;
                int dist_acum = cur.c + adj[j].c;

                #pragma omp critical (mindst_critical)
                {
                    minv = min_distance[adj[j].node];
                }

                // -1 = no value assigned = infinite
                if (minv == -1 || dist_acum < minv)
                {
                    #pragma omp critical (mindst_critical)
                    {
                        to_visit.erase(Line(v, minv));
                        vv_dist[i][v] = dist_acum;
                        min_distance[v] = dist_acum;
                        to_visit.insert(Line(v, dist_acum));
                    }
                }
            }
        }
    }
}
